import java.util.Arrays;
import java.util.HashSet;

/**
 * @author hewei
 * @version 1.0
 * @description: 1079. 活字印刷
 * @date 2022/11/10 15:18
 */

public class NumTilePossibilities {

    boolean[] flag;
    HashSet<String> set;
    char[] chars;
    int ans = 0;
    public int numTilePossibilities1(String tiles) {
        flag = new boolean[tiles.length()];
        chars = tiles.toCharArray();
        Arrays.sort(chars);
        temp();
        return ans;
    }

    public void temp() {
        for (int i = 0; i < chars.length; i++) {
            if (flag[i] || i > 0 && !flag[i - 1] && chars[i] == chars[i - 1]) continue;
            flag[i] = true;
            ++ans;
            temp();
            flag[i] = false;
        }
    }

    public void dfs(int i, StringBuilder stringBuilder) {
        if (i == chars.length) {
            if (stringBuilder.length() != 0) {
                set.add(stringBuilder.toString());
            }
            return;
        }
        dfs(i + 1, stringBuilder);
        for (int j = 0; j < chars.length; j++) {
            if (!flag[j]) {
                stringBuilder.append(chars[j]);
                flag[j] = true;
                dfs(i + 1, stringBuilder);
                flag[j] = false;
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
        }
    }

    int[] count;
    public int numTilePossibilities(String tiles) {
        count = new int[26];
        int n = tiles.length();
        for (int i = 0; i < n; i++) {
            count[tiles.charAt(i) - 'A']++;
        }
        return process();
    }

    public int process() {
        int res = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] == 0) continue;
            --count[i];
            ++res;
            res += process();
            ++count[i];
        }
        return res;
    }
}
